In order to calculate paths on a large-scaled network, database sizes in devices arranged in the network and the amount of network information to be exchanged among devices in the network become enormous. For example, with a routing protocol such as OSPF (Open Shortest Path First), in order to manage a detailed topology of the network, the number of nodes arranged in the network is limited up to about 100 nodes. Therefore, in many cases, the network is divided into a plurality of areas to reduce the number of nodes for managing the detailed topology of the network.
FIGS. 19A, 19B, 19C are explanatory diagrams of calculating a path over a plurality of divided areas in a communication network. In an example depicted in FIGS. 19A-19C, the network is divided into three areas 2a, 2b, and 2c, and path calculation and signaling are performed by using a routing protocol.
A path calculating device, defined as a device having a function for path calculation, summarizes information on the area including the path calculating device (the own area), and sends a notification indicating the summarized information to devices existing in areas other than the own area, so that network information is exchanged among devices in the network. In this way, the path calculating device can know the detailed information on the own area and the summarized information on areas other than the own area.
When path calculation is requested, a path calculating device in the area 2a including the start node determines such areas that are traversed by at least one path starting from the start node and reaching the end node, by using the summarized information. Thereafter, starting from the area including the start node toward the area including the end node, a path within an area (hereafter described as “an intra-area path”) is calculated for each area of the determined areas on the basis of the detailed information thereon, and the calculated intra-area path of the each area of the determined areas is set by signaling. In the examples of FIGS. 19A-19C, it is assumed that an end-to-end path to be calculated sequentially passes through areas 2a, 2b, and 2c. In the case, an intra-area path within the area 2a is first calculated using the detailed information and an intra-area path 3a is set by signaling, as depicted in FIG. 19B. Subsequently, calculation and signaling of an intra-area path are similarly performed for the area 2b, thereby setting a path 3b, as depicted in FIG. 19C.
The above mentioned calculation of an end-to-end path over a plurality of divided areas in a communication network can be performed by using a Path Computation Element (PCE). In the case of using the PCE, a passage area, which is defined as an area traversed by an end-to-end path to be calculated, is specified by a PCE in the area including the start node (hereafter described as “the start area”), and the PCE of each passage area calculates an intra-area path within the each passage area. That is, the PCE in the area including the end node (hereafter described as “the end area”) creates a tree indicative of connectibility among in-area paths with in the own area on the basis of the result of calculating the intra-area paths. Next, from the end area toward the start area a sub-tree that is connectable to the previously created sub-tree is sequentially created for each passage area, on the basis of the result of calculating intra-area paths. Thereafter, the shortest end-to-end path is selected from among end-to-end paths obtained by connecting the created sub-trees, and the selected end-to-end path is set by signaling.
FIG. 20 is an explanatory diagram of a path calculation method of two end-to-end paths using the backward recursive PCE-based computation (BRPC).
As a related path calculation method, backward recursive PCE-based computation (BRPC) is disclosed in the document of Networking Working Group Internet-Draft “A Backward Recursive PCE-based Computation (BRPC) procedure to compute shortest inter-domain Traffic Engineering Label Switched Paths” (draft-ietf-pce-brpc-06.txt). According to the method, as shown in FIG. 20, two end-to-end paths (a first end-to-end path 5 and a second end-to-end path 6) can be calculated. In FIG. 20, PCEs 4a, 4b, 4c, and 4d are provided for areas 2a, 2b, 2c, and 2d, respectively, and each of the two end-to-end paths starts from the start node, passes through four areas 2a, 2b, 2c, and 2d, and reaches the terminal node. For example, calculation of two end-to-end paths can be done by sequentially performing the following steps from (1) to (8) which correspond to (1)-(8) depicted in FIG. 20, respectively.    (1) The PCE 4a provided for the start area 2a requests a path calculation of area 2b to PCE 4b provided for area 2b through which an end-to-end path passes next to the area 2a. At this point, signaling is not performed and operation is limited to reception/transmission of request for calculating an intra-area path.    (2) PCE 4b requests a path calculation to PCE 4c provided for area 2c through which the end-to-end path passes next to area 2b.     (3) PCE 4c performs the similar operation in step (2).    (4) When PCE 4d receives a request for calculating an intra-area path, since PCE 4d is provided for the end area 2d, PCE 4d creates a sub-tree after calculating intra-area paths within the own area (end area 2d). The created sub-tree consisting of intra-area paths each connecting the terminal node with a node connectable to area 4c.     (5) After creating the sub-tree, PCE 4d sends information on the created sub-tree to PCE 4c as a response to the path calculating request from PCE 4c.     (6) PCE 4c calculates intra-area paths within the own area 2c. Then, based on the result of the calculation, PCE 4c creates a sub-tree consisting of intra-area paths each connecting a node connectable to area 2d with a node connectable to area 2b, and send information on the created sub-tree to PCE 4b.     (7) PCE 4b performs the similar operation.    (8) PCE 4a calculates intra-area paths within the own area 2a in response to the information given by PCE 4b, and creates a sub-tree of the own area 2a. 
Thereafter, PCE 4a selects an end-to-end path for communicably connecting between the start node and the end node by using the information on the sub-trees created by the PCEs provided for areas 2a to 2d. In this case, not all intra-area paths can be used as a part of a sub-trees to be created. For example, in area 2d, as denoted by a dotted lines in FIG. 20, when there are no resources for connecting the end node with a node connectable to next area 2c, an intra-area path 8 (denoted by a dotted line) cannot be used as a part of a sub-tree to be created.
It is possible to select, from a sub-tree created beforehand, a plurality of intra-area paths each used for a different end-to-end path. For example, an intra-area path used for the end-to-end path 5 and an intra-area path used for the end-to-end path 6 can be selected from the sub-tree 7, as depicted in FIG. 20. Selection of an intra-area path from the sub-tree can be performed on the basis of a cost value which is beforehand assigned to each intra-area path in the sub-tree.
Japanese Laid-open Patent Publication No. 2007-60461 discloses, as a related art of path calculation on a plurality of divided networks, a path setting method using a control node that is connected to a control network for controlling and setting transfer on a transmission network. The control node selects one of the boundary control nodes, as an exit node in the direction of the area in which the end node lies, on the basis of link information of the control network, and determines a path reaching the exit node on the basis of the link information of the transmission network.
Japanese Laid-open Patent Publication No. 2004-80211 discloses a method for setting a backup path not having a shared link with a main path between the start node and the end node by providing the priority among boundary nodes and by keeping collaboration among the area boundary nodes.
Japanese Laid-open Patent Publication No. 2004-23179 discloses a method for calculating an exclusive path with the minimal sum of metrics of two paths when a protection type is (1+1) and further discloses a method for calculating a pair of paths with the minimal metrics on the premise of using the pair of paths ensuring an exclusive backup path against the current path, when the protection type is 1:1 or 1:N.